package middle;

import util.PrintUtils;

public class Solution_221 {

    public int maximalSquare(char[][] matrix) {
        int rst = 0;
        int[][] array = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int length = 0;
                if (matrix[i][j] == '1') {
                    length = 1;
                    if (i > 0 && j>0 && array[i-1][j-1] > 0) {
                        for (; length <= array[i - 1][j - 1]; length++) {
                            if (matrix[i][j-length] == '0' || matrix[i - length][j] == '0') {
                                break;
                            }
                        }
                    }
                }
                array[i][j] = length;
                rst = Math.max(rst, array[i][j]);
            }
        }
        return rst * rst;
    }

    public static void main(String[] args) {
        Solution_221 model = new Solution_221();
        System.out.println(model.maximalSquare(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));
        System.out.println(model.maximalSquare(new char[][]{{'0','1'},{'1','0'}}));
        System.out.println(model.maximalSquare(new char[][]{{'0'}}));
//        PrintUtils.transfer("[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]");
    }
}
